package LimitedTimeGame.Day_0209;

/**
 * @author zxc
 * @date 2023/02/09 09:47
 **/

import java.util.HashMap;
import java.util.HashSet;

/**
 * 题目 ：链表中环的入口节点
 * 题目详述 ：
 * 给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回null。
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
 * 说明：不允许修改给定的链表。
 *
 * 提示：
 * 链表中节点的数目范围在范围 [0, 104] 内
 * -105 <= Node.val <= 105
 * pos 的值为 -1 或者链表中的一个有效索引
 */
public class DetectCycle {
    /**
     * 思路 ：
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head){
        // 1.哈希表 ：即，使用哈希表来存储链表中的节点，若是遇到重复的链表结点的话，则代表了当前节点为链表环的起始节点;
//        HashSet<ListNode> hashSet = new HashSet<>();
//        while(head != null){
//            if(hashSet.contains(head)){
//                return head;
//            }
//            hashSet.add(head);
//            head = head.next;
//        }
//        return head;

        // 2.快慢指针
        /**
         * 核心思想 ：
         * a，指的是链表头结点head到环入口节点距离;
         * b,指的是双指针相遇节点与环入口节点之间的距离;
         * c,指的是(环长度 - b);
         * （1）slow和fast指针相遇;（slow指针所走距离的两倍 == 快指针所走距离;）
         *  ===> 2 * (a + b) = a + b + n * (b + c);
         *  ===> a = c + (n - 1) * (b + c);
         *  注意 ：n必须满足 ：n >= 1;
         *  <===> 等价于，头结点到环入口节点之间距离a == 双指针相遇节点到环入口节点之间距离c + (n - 1)倍的环长度 b + c;
         *
         * （2） fast指针指向虚拟头结点 && slow指针指向双指针相遇节点,以相同速度进行移动，直至fast指针和slow指针相遇，相遇节点===》 链表中的环入口;
         *  ===》 fast指针向环入口节点移动过程中，同时slow指针也在向环入口节点移动;
         *  若是slow指针到达环入口节点时，fast指针还未到的话，则会继续在环中进行循环遍历;
         *
         */
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                fast = dummy;
                while(fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
    class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
    }
}
